\documentclass{article}
\usepackage{ctex}
\usepackage{xcolor}
\usepackage{listings}
\usepackage{amsthm,amsmath,amssymb}
\usepackage{mathrsfs}
\usepackage{geometry}
\usepackage{titlesec} 
\usepackage{graphicx}
\usepackage[colorlinks,linkcolor=black]{hyperref}
\definecolor{commentcolor}{RGB}{85,139,78}
\definecolor{stringcolor}{RGB}{206,145,108}
\definecolor{keywordcolor}{RGB}{34,34,250}
\definecolor{backcolor}{RGB}{220,220,220}
\geometry{left = 2.0cm, right = 2.0cm, top = 2.5cm, bottom = 2.5cm}
% \title{NLP实验1: 最短编辑距离}
% \author{姓名:隋佳成 \and 班级:人工智能91 \and 学号:2193712551}
% \date{\today}

\usepackage{accsupp}	
\newcommand{\emptyaccsupp}[1]{\BeginAccSupp{ActualText={}}#1\EndAccSupp{}}

\usepackage{listings}
\lstset{						        %高亮代码设置
	language=python, 					%Python语法高亮
	linewidth=0.9\linewidth,      		%列表list宽度
	%basicstyle=\ttfamily,				%tt无法显示空格
	commentstyle=\color{commentcolor},	%注释颜色
	keywordstyle=\color{keywordcolor},	%关键词颜色
	stringstyle=\color{stringcolor},	%字符串颜色
	%showspaces=true,					%显示空格
	numbers=left,						%行数显示在左侧
	numberstyle=\tiny\emptyaccsupp,		%行数数字格式
	numbersep=5pt,						%数字间隔
	frame=single,						%加框
	framerule=0pt,						%不划线
	escapeinside=@@,					%逃逸标志
	emptylines=1,						%
	xleftmargin=3em,					%list左边距
	backgroundcolor=\color{white},	    %列表背景色
	tabsize=4,							%制表符长度为4个字符
	gobble=4							%忽略每行代码前4个字符
	}

\begin{document}
    \newpagestyle{main}{            
        \sethead{}{自然语言处理及应用实验报告}{}     %设置页眉
        \setfoot{}{\thepage}{}                     %设置页脚，可以在页脚添加 \thepage  显示页数
        \headrule                                  % 添加页眉的下划线                                      %添加页脚的下划线
    }
    \pagestyle{main}                               %使用该style
    111
    \clearpage
    % \maketitle
    \section*{\kaishu{一 \quad 实验目的}}
        本次实验是文本分类实验，旨在使用传统的机器学习方法来处理网络新闻的分类，其中包含了朴素贝叶斯和KNN的方法。本次实验完整的代码及数据可以在
        我的gitee仓库
        \url{https://gitee.com/jia_cheng_sui/text-classification.git}找到。

    \section*{\kaishu{二 \quad 实验环境}}
    Windows10操作系统, VSCode
    \section*{\kaishu{三 \quad 实验方法}}
    \subsection*{3.1 \quad 函数介绍}
    文件jupyter\_version.ipynb实际上是朴素贝叶斯分类器的实现以及训练、验证、预测。在文件jupyter\_version.ipynb中有下列类和方法，现讲述其功能。
    \begin{enumerate}
        \item[-] class GetStopWrods用于由文件返回停用词列表，初始化时不需要进行任何参数传递，使用时给定停用词文件所在的路径即可返回停用词列表。
        \item[-] class Cut用于利用停用词表返回经过分词后的文章所包含的词列表。在初始化时需要给定停用词列表。在这个类中，包含如下方法：
        \begin{enumerate}
            \item def replaceWithStopWordsAndRegex(self, filename)将会返回一个经过正则化处理的字符串，输入信息由filename，指的是需要分类的文本，该方法将过滤掉文本中的邮箱，还将过滤掉新闻文本中的
                前几行关于新闻出处等信息而不是新闻内容的信息。并且，该方法将一些无意义的特殊字符替换成空格。
            \item def cutWords(self, filename)将会返回一个经过正则化和停用词过滤之后的单词列表。该方法首先调用replaceWithStopWordsAndRegex方法对输入文本作正则化和特殊字符处理，然后通过停用词表对单词列表进行过滤。
            \item def wordStemming(self, listOfF)用于寻找单词的词根，但是考虑到这里会调用nltk库，我尽量不想调用外界库做这个实验，并且试了下效果，经过词根提取的分类效果也不会提升很大，所以真正实验没有调用此方法。
        \end{enumerate} 
        \item[-] def sampleNFold(totalNumber, N = 5)用于生成交叉验证的N折数据索引集。totalNumber指的是数据一共多少个，N指的是需要多少折。最后会返回一个列表，列表的尺寸为(N, totalNumber // N), 注意，返回的列表中的元素均为range(0,totalNumber)
                之一，指的是数据的索引。 
        \item[-] class SetProbability()是朴素贝叶斯分类器，名字看起来还是设置概率，其实是我一开始想概率计算和分类器分开两个类写，但是后来决定合在一起写，所以类的名字没有改。该类中的一些方法如下：
        \begin{enumerate}
            \item def computeF1Score(self)用于计算分类器的F1度量，需要注意的是，这是一个二十分类的任务，所以我们计算平均F1度量。
            \item def clearLastFold(self)用于清空上一折残留的信息。
            \item def setWordsContainer(self, kth)用于建立词袋(bag of words)，需要注意的是，我建立了多个词袋，即一个总的词袋，包含20类中所有训练集中的单词列表中的词，还有20个分词带，分词带只包含该类中的词。之所以
                这样做，是因为，我发现如果在计算条件概率的时候使用总词袋进行所以，由于词袋过大(大概由20万个token左右)，会出现内存跑爆的现象，程序就被kill掉无法继续训练。故我们在这里建立分词带用于后面计算条件概率用。
            \item def setWordsDictionary(self)用于利用setWordsContainer得到的词袋信息建立单词的索引，也就是单词列表转化为vector时，各个单词所在的位置。同样的，我们建立了一个总单词索引字典和20个分单词索引字典。
            \item def setBoolMatrix(self)用于建立布尔矩阵，即将各个类中各文本得到的各单词列表，通过上面建立的索引字典，将单词列表转化为单词向量vector，并将同一类的vectors合并成一个矩阵。这样我们能得到20个类布尔矩阵。注意，在这一步，我们都是利用分单词索引字典
                来设置布尔值。
            \item def setConditionalProbability(self)利用前面得到的布尔矩阵建立条件概率向量。就是将各个类布尔矩阵中的向量按位置相加，最后每个位置都除以类布尔矩阵中1的中总数。
            \item def train(self)通过调用分类器中其他方法来进行训练。
            \item def predict(self, filepath)通过训练好的模型进行预测，filepath是需要预测分类的文件路径。
            \item def verify(self, kth)是第kth步交叉验证。注意，训练用到的数据是N折中的N-1折，验证用的是训练过程中没见过的数据。 
        \end{enumerate}
    \end{enumerate}

    文件KNN\_subset\_version.ipynb实际上是KNN分类器的实现以及训练、验证、预测过程。在此文件中大部分类和方法除了在具体分类方法(KNN是距离计算，朴素贝叶斯是条件概率计算)上有些不同，其余部分大致相同。相较来说多了一个用于排序时比较大小的方法。
    还有一点需要说明，由于KNN计算十分慢，如果用全部的20类每类1000个文本，那我的电脑跑的太慢了，而且很可能内存也会爆掉，所以我缩减了数据量，只截取了6个类，每个类截取了700篇文本，这也是为啥叫subset version。
    \begin{enumerate}
        \item[-] def takeFirst(item)用于排序时用，实际上表示KNN中距离远近程度。
    \end{enumerate}

    \subsection*{3.2 \quad 算法介绍}
    本次实验牵扯到的算法有两个，一个是朴素贝叶斯，另一个是KNN。
    下面一个一个地介绍。
    \begin{enumerate}
        \item[-] 朴素贝叶斯：假设数据的特征属性是$X = \{x_0, x_1, \dots x_n\}$，在我们文本分类中，这个特征属性其实就是单词vector，可能的类别是$Y = \{y_0, y_1, \dots y_m\}$，那么分类时需要计算的就是$$P(Y|X) = \frac{P(X|Y) \times  P(Y)}{P(X)}$$
                实际上，分母$P(X)$的部分可以忽略，所以，我们要计算的就是分子的部分，又因为我们在交叉验证划分数据的时候是将每一类以同样的比例和数量划分出来的，所以$P(Y)$是相等的，所以我们只需要关注$P(X|Y)$部分，这也就是我们分类器里面计算的条件概率部分。
                在上面的式子中我们用的都是向量的形式，实际上写的更加明确一点就是找到使得$P(X|y_i)$最大的$y_i$类。
        \item[-] KNN：K最邻近算法，其思想就是当一个陌生的分类器没见过的数据到来的时候，寻找与他最相邻的K个数据点，这K个数据点就像投票一样，把多数类作为陌生数据的类。那么主要就在于怎样计算两个数据点之间的距离，这里我选择使用两个单词向量的内积的倒数来表示两个
                两个文本之间的距离，两个文本具有的单词越相似，其内积越大，内积的倒数也就越小，距离越小。 

    \end{enumerate}
    % \lstset{numbers=left, 
    % numberstyle=\tiny, 
    % keywordstyle=\color{blue!70},commentstyle=\color{red!50!green!50!blue!50}, 
    % frame=shadowbox, 
    % rulesepcolor=\color{red!20!green!20!blue!20} 
    % } 
    \subsection*{3.3 \quad 编程实现}
    由于此次编程的代码量较大，不易在报告中体现，所以将代码源文件放在了文件夹中，可以到相应的文件夹下查看。除去上面两个介绍的文件，我还提供了一个KNN-jupyter-version.ipynb文件，这个文件是用的全20类各类1000各文件训练的KNN，不是用的子集，
    但是遗憾的是，由于我电脑算力和内存的限制，无法用全集进行交叉验证，只能做单个的预测，而且即使只是单个的预测，跑起来也相当慢，所以不建议尝试这个文件，还是以上面两个文件为主。
    \begin{lstlisting}
    
    \end{lstlisting} 
    \section*{\kaishu{四 \quad 实验结果}}
    下面的各个实验结果都可以在文件夹或者jupyter文件中查看，在此报告中仅展示部分结果。

    \begin{figure}[h!]
        \centering
        \includegraphics[width = 0.8\linewidth]{BayesVersion.png}
        \caption{朴素贝叶斯其中一折的结果}
        \label{fig:bayesversion}
    \end{figure}

    如图\ref{fig:bayesversion}显示了朴素贝叶斯分类器其中一折的结果，可以看到F1分数达到了0.8以上，还是不错的。第一行的一个数表明了token的总数，下面连着几行表明了分类器内部训练的过程。在验证完毕时打印出正确分类数和错误分类数以及F1
    分数。并且将把训练得到的困惑矩阵以csv的格式保存到同一文件路径下。
    \begin{figure}[h!]
        \centering
        \includegraphics[width = 0.8\linewidth]{KNNSubsetVersion.png}
        \caption{KNN其中两折的结果}
        \label{fig:KNNSubsetVersion}
    \end{figure}

    如图\ref{fig:KNNSubsetVersion}显示了KNN其中两折的结果，第一行是所有token的总数，注意，由于我们使用的是数据集全集的子集，所以token相较贝叶斯版本的少了很多，但是我们可以看到F1分数仍然较高，大概能保持在0.75以上。
    为了可视化一下，我们使用predict方法来预测一下rec.sport.hockey中的一个文件，可以看到预测成功，后面的0.9表示KNN中投票为rec.sport.hockey所占比例。
    
    每一折的困惑矩阵都被保存了下来，可以从文件夹中查看，如图所示，名字中不带KNN的是朴素贝叶斯分类器所得到的困惑矩阵，带KNN的就是KNN得到的困惑矩阵。
    \begin{figure}[h!]
        \centering
        \includegraphics[width = 0.9\linewidth]{confusionMatrixs.png}
        \caption{困惑矩阵}
        \label{fig:confusionMatrixs}
    \end{figure}
    \begin{figure}[h!]
        \centering
        \includegraphics[width = 0.9\linewidth]{BayesConfusionMatrix.png}
        \caption{Bayes困惑矩阵}
        \label{fig:BayesconfusionMatrixs}
    \end{figure}

    从图\ref{fig:BayesconfusionMatrixs}中可以看出，对角线占去总数的大多数，也是符合我们分类的预期的。

    \begin{figure}[h!]
        \centering
        \includegraphics[width = 0.9\linewidth]{KNNConfusionMatrix.png}
        \caption{KNN困惑矩阵}
        \label{fig:KNNconfusionMatrixs}
    \end{figure}

    从图\ref{fig:KNNconfusionMatrixs}中可以看出，rec.sport.hockey和rec.sport.baseball容易混淆，这也是容易理解的，毕竟都是运动种类的一种，可能有更高概率的词频重叠。
    \section*{\kaishu{五 \quad 遇到问题及解决思路}}
    \subsection*{5.1 \quad 内存跑爆}
    由于全集的token量过于庞大，一开始我在写代码的时候在计算布尔矩阵的时候使用全局token作为索引的，也就是大概19~20万个token左右，但是这样会迅速消耗掉我所有的内存，根本跑不起来，程序就会被kill掉。
    所以我只能每个类建立一个索引，这样才能够将布尔矩阵存下来。
    \subsection*{5.2 \quad 概率太小以至于变为0.0}
    我在使用已经训练好的朴素贝叶斯分类器计算单词向量在各个类中的条件概率的乘积时，出现了所有类的概率乘积都是0的情况，研究发现这是python小数极限造成的，下面细说。
    python中能够比较大小的最小小数大致在$10^{-300}$左右，而由于token数目很大，当出现足够多的类字典之外的词的时候，就需要使用加一平滑，所以最后得到的概率会很小，可能会小于python的极限，此时这个概率就会变成0，
    不是他真的是零，而是超过了python的表示范围后python就将他当成0处理。于是这个时候我们再去比较大小就没有意义了，所以我在记录单词向量在各个类中的条件概率乘积之外，还用一个Unseen变量来记录该单词向量在各个类中没有见过的单词数量。
    当该单词向量在所有类中的概率乘积都超出python极限时，我们就是用这个Unseen来估计该单词向量属于哪个类，也就是说Unseen最小的那个类就是该单词向量所属的类。
\end{document}
